package com.my.interview;


import java.util.Hashtable;

/**
 * LRUCache (Least Recent Userd) algorithm 的存储是基于双向链表实现的
 * 其中head表示双向链表的头部，tail表示尾部。首先预设LRU的容量，
 * 如果存储满了，可以通过O(1)算法淘汰掉tail，每次新增访问，访问数据增加到头部，
 * 若链表中已经存在该数据，则直接移动到头部
 * use HashMap and double linked list to implement it
 *
 */
public class LRU {

    private Hashtable<String, DoubleLinkedList> cache = new Hashtable<>();

    /**
     * 目前包含的数量
     */
    private int count;
    /**
     * LRU算法的容量
     */
    private int capacity;

    private DoubleLinkedList head, tail;

    public LRU(int capacity) {
        this.capacity = capacity;
        this.count = 0;

        head = new DoubleLinkedList();
        tail = new DoubleLinkedList();

        head.setPrev(null);
        tail.setNext(null);

        head.setNext(tail);
        tail.setPrev(head);
    }

    public int get(String key){
        DoubleLinkedList node = cache.get(key);
        if(node == null){
            return -1;
        }
        moveToHead(node);
        return node.getValue();
    }

    public void set(String key, int value){

        DoubleLinkedList node = cache.get(key);
        if(node == null){
            DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
            doubleLinkedList.setKey(key);
            doubleLinkedList.setValue(value);
            doubleLinkedList.setPrev(null);
            doubleLinkedList.setNext(head);
            head.setPrev(doubleLinkedList);
            head = doubleLinkedList;
            cache.put(key, doubleLinkedList);
            count++;
            if(count > capacity){
                cache.remove(tail.getKey());
                tail = tail.getPrev();
            }
        }else{
            node.setValue(value);
            moveToHead(node);
        }
    }


    public void moveToHead(DoubleLinkedList node){

        node.getPrev().setNext(node.getNext());
        node.getNext().setPrev(node.getPrev());

        node.setPrev(null);
        node.setNext(head);
        head.setPrev(node);
        head = node;
    }

    public void printDoubleLinkedList(){
        DoubleLinkedList doubleLinkedList = head;
        while (doubleLinkedList.getNext() !=null){
            System.out.print(doubleLinkedList.getValue());
            doubleLinkedList = doubleLinkedList.getNext();
        }
        System.out.println();
    }

    public static void main(String[] args) {

        LRU lru = new LRU(3);
        lru.set("1",1);
        lru.set("2",2);
        lru.set("3",3);
        lru.printDoubleLinkedList();
        lru.set("1",4);
        lru.printDoubleLinkedList();

    }
}
